package cn.edu.zufe.mjt.dfs;

import java.util.*;

/**
 * 深度优先搜索——全排列问题
 * DFS 时刻注意理解递归树，以及如何剪枝。
 */
public class AllArrangements {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        List<List<Integer>> permute = permute(nums);
        for (List<Integer> path : permute) {
            System.out.println(path);
        }
    }

    public static List<List<Integer>> permute(int[] nums) {
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        List<List<Integer>> paths = new ArrayList<>();
        return dfs(nums, used,new ArrayList<>(), paths);

    }

    public static List<List<Integer>> dfs(int[] nums, boolean[] used,List<Integer> res, List<List<Integer>> paths) {
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                res.add(nums[i]);
                dfs(nums, used,res, paths);
                used[i] = false;
                res.remove(res.size() - 1);
            }
        }
        if (res.size() == nums.length) {
            paths.add(new ArrayList<>(res));
        }
        return paths;
    }
}
